1. Field of the Invention
The present invention relates generally to the field of image reproduction, and more particularly to digital halftoning. Still more particularly, the present invention relates to a method and apparatus for color halftoning.
2. Description of the Prior Art
A printed color image is a field of tiny dots of typically only four colors of ink arranged meticulously so as to replicate the multiplicity of colors within the color image. Since only four colors of inks are available, it is generally not possible to reproduce a color image exactly like its original. But exact duplication is not necessary. One need only create a believable image, and the human eye and brain will compensate for differences in illumination, color surroundings and tonal range.
Tonal range is important in creating a believable image. Some imaging devices are capable of reproducing acceptable tone directly. Examples of such devices include photography and television. These types of imaging devices can produce continuous tone, or "contone."
Other imaging devices are not able to reproduce acceptable tone directly. These types of devices are typically "binary" or "bi-level" devices and multi-level devices. Bi-level devices produce at any output position only two values; one value corresponds to "on", the other value to "off." One example of a bi-level device is a dot matrix printer. Multi-level devices typically have more than two output values but not as many output values as contone devices. In other words, multi-level devices are devices that have M output values for N input values, where N&gt;M.
Bi-level and multi-level devices have limited tonal range. Intermediate tones, such as varying shades of gray, must be represented by halftones. Halftoning is a process by which continuous-tone colors are approximated by a pattern of pixels that can achieve only a limited number of discrete colors. The most familiar case of this is the rendering of gray tones with black and white pixels, as in a newspaper photograph.
A halftone pattern is made up of a region of pixels referred to as the halftone cell. In conventional digital halftoning (halftoning that uses rational tangent angles), the halftone cell contains a specific, repeatable pattern. The tonal range of a halftone pattern depends upon the number of pixels in the halftone cell.
Pixels are usually arranged on an orthogonal grid, with the pixels placed at evenly spaced lattice points on an output device. A two dimensional array of pixels is often called a pixel map or pixmap. Each pixel in the pixmap has its own unique address on the grid. An image processor uses this address to keep track of each pixel and its associated threshold value.
A threshold value represents the tone value at which the pixel is turned "on." Each pixel within a halftone cell is assigned a threshold value. Typically a threshold array is used to control the individual pixels in a halftone cell. A threshold array can contain one or more halftone cells. The threshold array is replicated and "tiled" (i.e., filled in a non-overlapping manner) over the entire device space. Each pixel in the device space is then mapped to a particular element of the threshold array.
Within any given halftone cell in an image, a certain percentage of the pixels may be "on" and the remaining pixels may be "off." The percentage of pixels that are "on" correspond to the tonal value that the cell represents. For example, if sixty percent of the pixels in a given cell are "on", sixty percent of the pixels in that cell are black and the rest are white. "Black" means solid, or fully saturated. This cell emulates a sixty percent gray tint.
In order to determine whether a pixel is "on" or "off", an imaging device checks a pixel's address, determines the tonal value of the image at that address, and compares the tonal value with the pixel's threshold value in the threshold array. If the tonal value exceeds the threshold value, the pixel is turned "on" when the image is created on the output device.
For each pixel in an image, there is a trade-off between the size of a halftone cell and tonal resolution: the smaller the halftone cell, the smaller the number of pixels it contains, and the fewer tonal values it can represent. Thus, for the best tonal resolution (i.e., the most gray levels), the halftone cell should be large so as to include as many pixels as possible. On the other hand, the bigger the halftone cell, the more visible it becomes to the human eye, distorting the picture at times. This trade-off between number of gray levels and halftone cell size is one of the classic problems of halftoning.
Some color devices, such as color printers, are multi-level devices and have a limited tonal range. Color printers typically have cyan, magenta, yellow and black as the available ink colors. Cyan, magenta and yellow are transparent inks, while black is opaque. Intermediate tones, or varying shades of color, must be represented by halftones. Halftoning in color devices presents added complexity over that of monochromatic imaging.
For example, mechanical misregistration between color planes can cause color shifts. For many types of printers, such as pre-press and inkjet, mechanical misregistration can occur by having the paper feed at an angle, having the paper slide side to side or in the direction of paper movement. This is especially problematic when opaque pixels inadvertently obscure transparent pixels. Mechanical misregistration between color planes can also cause "beat" effects which are known as Moire patterns. Moire patterns are interference patterns that can occur when two or more halftone screens are superimposed.
One method used to reduce the effects of mechanical misregistration is to use a halftone screen having a unique frequency and angle for each ink plane. For example, if there are three colors available, one screen may be offset 30 degrees from the underlying screen, and the second screen may be offset 60 degrees from the underlying screen. This solution, however, creates a different type of Moire pattern, one known as rosettes. Rosettes are undesirable because they impart a low resolution effect on the resulting output. For more information on halftoning, Moire effects and rosettes, see PostScript.TM. Screening: Adobe Accurate Screens.TM. (1992) by Peter Fink, ISBN 0-672-48544-3.
Unlike inkjet and prepress printers, laser printers have only one predominate type of mechanical misregistration, those that occur in the direction of paper movement. Because mechanical misregistration occurs only in the direction of paper movement, the use of line screens allows for controlling the overlap between transparent and opaque inks without using screens placed at different angles from each other. Such line screens place the toner (i.e., ink) in lines that parallel the direction of paper movement. One problem with line screens, however, is that the placement of the lines must be controlled. Also, the lines must be very thin in order to get a sufficient number of gray levels in very light areas. For example, to obtain 256 levels of gray, the thickness of the line must be controllable to at least 1/256 of full line width. Printing very thin lines can be difficult, if not impossible, for laser printers.
When color inks are added to the output, the problems of controlling line placement and line thinness only intensifies. This is especially true for light color areas, because hue shifts can occur. Hue shifts occur when one color fades out too quickly, and are undesirable because hue shifts alter, sometimes significantly, the quality of a color picture.